package com.sakura.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Code01_找到K个最接近的元素 {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(new Code01_找到K个最接近的元素().findClosestElements_3(arr, 4, 3));
    }

    // 双指针 排除法
    public List<Integer> findClosestElements_1(int[] arr, int k, int x) {
        int n = arr.length;
        int left = 0;
        int right = n - 1;
        // k 是保留的数
        int removeNum = n - k;
        while (removeNum > 0) {
            if (x - arr[left] <= arr[right] - x) {
                right--;
            } else {
                left++;
            }
            removeNum--;
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            ans.add(arr[i]);
        }
        return ans;
    }

    // 滑动窗口
    public List<Integer> findClosestElements_2(int[] arr, int k, int x) {
        // sum 符合题意的和比不符合题意的和要小
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        int idx = 0; // 表示符合题意的数据起点
        for (int l = 0, r = 0; r < arr.length; r++) {
            sum += Math.abs(arr[r] - x);
            if (r - l + 1 == k) {
                if (sum < ans) {
                    ans = sum;
                    idx = l;
                }
                sum -= Math.abs(arr[l++] - x);
            }
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = idx; i < idx + k; i++) {
            list.add(arr[i]);
        }
        return list;
    }

    public List<Integer> findClosestElements_3(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - k;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            list.add(arr[i]);
        }
        return list;
    }
}
